En primer lugar necesitamos ordenar todas las aritas, lo que nos cuesta, utilizando la funci\'on \textit{sort} de la libreria estandar de C, $O(M log_2(M))$. Para nuestro caso sabemos, por el enunciado, que tenemos un total de $\frac{N(N-1)}{2}$ aristas, siendo N la cantidad de ciudades (nodos). Ordenar esta lista nos cuesta entonces: $O(\frac{N(N-1)}{2} * log_2(\frac{N(N-1)}{2}))$ lo que es igual a $O(N^2 * log_2(N^2)) = O(N^2 * 2(log_2(N)))$ o sea $O(N^2*log_2(N))$.

Luego iteramos nuestra lista de rutas ($O(N^2)$ en el peor caso), y en cada iteraci\'on realizamos la operacion \textit{combinar} y operaciones de asignaci\'on (que nos cuestan O(1)). Luego la complejidad del ciclo es: lo que tarde la operaci\'on \textit{combinar} * $O(N^2)$  en el peor caso.

La operacion \textit{combinar} realiza dos ciclos, en los que 'sube' con un puntero p1 desde un nodo(correspondiente a la ciudad pasada por parametro) hasta la raiz del arbol. Esto tarda $O(H)$ en el peor caso, siendo H la altura del arbol a recorrer.

Como trabajamos con \'arboles m-\'arios no tenemos una cantidad maxima de nodos por nivel, por lo que analizaremos el peor caso, es decir cuando la altura del \'arbol crece con la menor cantidad de nodos posibles.

Dada la forma en que vamos combinando los arboles, sabemos que la altura s\'olo puede aumentar cuando ambos arboles tienen la misma altura. Luego si queremos combinar 2 \'arboles con un \'unico nodo (altura 0), obtenemos un arbol de altura 1. Si repetimos de nuevo este procedimiento, con dos \'arboles de altura 1 (2 nodos en cada arbol), obtenemos un nuevo arbol de altura 2, con un total de 4 nodos.

Vemos entonces que a medida que aumenta la altura, se duplica la cantidad de nodos, es decir, para un \'arbol de altura h tenemos en total 2^h cantidad de nodos, o lo que es lo mismo, para N cantidad de nodos la altura del \'arbol es $log_2(N)$.

Luego la complejidad de la operaci\'on combinar es $2 * log_2(N)$, es decir $log_2(N)$.
 
